package Class027;

import BasicDataStructures.ListNode;
import Utils.ListUtils;

import java.util.*;

public class HeapQuestions {
    public static void main(String[] args) {
        int[] d1 = {1,3,5,7};
        int[] d2 = {-2,10,20};
        int[] d3 = {0,9,12,15,19};
        ListNode head1 = ListUtils.generateList(d1);
        ListNode head2 = ListUtils.generateList(d2);
        ListNode head3 = ListUtils.generateList(d3);
        ListNode[] heads = {head1, head2, head3};
        ListUtils.printList(mergeKSortedLists(heads));

        int[][] segs = {
                {5,9},
                {2,6},
                {1,5},
                {3,7},
                {1,3},
                {2,4},
        };
        List<List<Integer>> ranges = ListUtils.generateSegments(segs);
        System.out.println(mostOverLaps(ranges));

        int[] arr = {20, 500, 50, 50};
        System.out.println(minOpToHalf(arr));
    }

    //1. 合并K个有序链表
    //K条链表，共n节点
    //O(N) + O(N * logK) => O(NlogK)
    public static ListNode mergeKSortedLists(ListNode[] heads) {
        if(heads == null) return null;
        if(heads.length == 1) return heads[0];
        PriorityQueue<ListNode> pq = new PriorityQueue<>(Comparator.comparingInt(n -> n.val));
        for(ListNode node: heads) {
            pq.offer(node);
        }
        ListNode dummyHead = new ListNode(-1);
        ListNode cur = dummyHead;
        while(!pq.isEmpty()) {
            ListNode n = pq.poll();
            cur.next = n;
            cur = cur.next;
            if(n.next != null) {
                pq.offer(n.next);
            }
        }
        return dummyHead.next;
    }

    //2. 线段最多重合问题
    public static int mostOverLaps(List<List<Integer>> ranges) {
        PriorityQueue<Range> starts = new PriorityQueue<>((r1, r2) ->
                r1.s != r2.s ? r1.s - r2.s : r1.e - r2.e);
        PriorityQueue<Range> overLaps = new PriorityQueue<>(Comparator.comparingInt(r -> r.e));
        for(List<Integer> range: ranges) {
            starts.offer(new Range(range.get(0), range.get(1)));
        }
        int max = 0;
        while(!starts.isEmpty()) {
            Range cur = starts.poll();
            while(!overLaps.isEmpty() && overLaps.peek().e <= cur.s) {
                overLaps.poll();
            }
            overLaps.offer(cur);
            max = Math.max(max, overLaps.size());
        }
        return max;
    }

    public static class Range {
        int s;
        int e;

        public Range(int s, int e) {
            this.s = s;
            this.e = e;
        }
    }

    //3. 让数组整体累加和减半的最少操作数
    //[20, 100, 50, 50] 累加和是220
    //每一个操作可以让其中一个数减半，比如选了100，那么100就变成了50,累加和此时是170
    //问最少多少次可以让220减少到 <= 110?
    //很明显贪心，每次选里面最大的就行
    public static int minOpToHalf(int[] arr) {
        double target = 0;
        for(int i : arr) target += i;
        Heap heap = new Heap(arr);
        target /= 2;
        int steps = 0;
        while(target > 0) {
            target -= heap.adjustLargest();
            steps++;
        }
        return steps;
    }

    //大顶堆
    public static class Heap {
        public double[] heap;
        public int size;

        public Heap(int[] arr) {
            size = arr.length;
            heap = new double[size];
            for(int i = arr.length - 1; i >= 0; i--) {
                add(arr[i], i);
            }
        }

        public double adjustLargest() {
            int index = 0;
            double res = heap[index] / 2;
            heap[index] /= 2;
            adjust(index);
            return res;
        }

        private void adjust(int index) {
            sinkDown(heap, index, size);
        }

        private void add(double val, int index) {
            heap[index] = val;
            sinkDown(heap, index, size);
        }

        private void sinkDown(double[] arr, int index, int size) {
            int left = (index << 1) + 1;
            while(left < size) {
                int right = left + 1;
                int next = right < size && arr[right] > arr[left] ?
                        right : left;
                if(arr[index] < arr[next]) {
                    swap(arr, index, next);
                    index = next;
                    left = (index << 1) + 1;
                }else {
                    break;
                }
            }
        }

        private void swap(double[] arr, int x, int y) {
            double temp = arr[x];
            arr[x] = arr[y];
            arr[y] = temp;
        }
    }

}
